package com.cat.graphTheory;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/6UEx57/description/
 * @create 2025/9/23 10:10
 * @since JDK17
 */

public class Solution23 {
    public int conveyorBelt(String[] matrix, int[] start, int[] end) {
        int n = matrix.length, m = matrix[0].length();
        int[][] dis = new int[n][m], dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        HashMap<Character, int[]> map = new HashMap<>();
        map.put('^', dir[0]);
        map.put('v', dir[1]);
        map.put('<', dir[2]);
        map.put('>', dir[3]);
        char[][] g = new char[n][m];
        for (int i = 0; i < n; i++) {
            g[i] = matrix[i].toCharArray();
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.add(start);
        dis[start[0]][start[1]] = 0;
        while (!q.isEmpty()) {
            var p = q.pollFirst();
            var cur = map.get(g[p[0]][p[1]]);   // 原方向
            int dist = dis[p[0]][p[1]]; //
            if (p[0] == end[0] && p[1] == end[1]) { // 找到了
                return dist;
            }
            for (var d : dir) {
                int nx = p[0] + d[0], ny = p[1] + d[1];
                if (nx == -1 || nx == n || ny == -1 || ny == m) {   // 越界
                    continue;
                }
                if (d[0] == cur[0] && d[1] == cur[1]) { // 原来的方向
                    if (dist < dis[nx][ny]) {
                        dis[nx][ny] = dist;
                        q.addFirst(new int[]{nx, ny});
                    }
                } else {    // 更改方向
                    if (dist + 1 < dis[nx][ny]) {
                        dis[nx][ny] = dist + 1;
                        q.addLast(new int[]{nx, ny});
                    }
                }
            }
        }

        return -1;
    }
}
